#include "allocator_interface.h"
#include "allocator_defines.h"
#include "config.h"

/* Returns true if p is ALIGNMENT-byte aligned */
#if (__WORDSIZE == 64 )
#define IS_ALIGNED(p)  ((((uint64_t)(p)) % ALIGNMENT) == 0)
#else
#define IS_ALIGNED(p)  ((((uint32_t)(p)) % ALIGNMENT) == 0)
#endif

/* 
 * Returns the floor of log2(v). Defined only for unsigned 32-bit integers with 
 * value greater than 1.
 */
static int logbase2(uint32_t v) {
  static const int MultiplyDeBruijnBitPosition[32] = 
  {
    0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
    8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
  };
  v |= v >> 1; // first round down to one less than a power of 2 
  v |= v >> 2;
  v |= v >> 4;
  v |= v >> 8;
  v |= v >> 16;
  return MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];
}

namespace my
{
  /*
   * For each index i, contains the number of blocks in freeLists[i] which
   * have not yet been found in the memory (used strictly in heap checking).
   * The last free list always contains (void *)-1, so this is checked 
   * separately.
   */
  static int freeListCounter[NUM_FREE_LISTS - 1];
  static int threadFreeListCounter[NUM_THREAD_FREE_LISTS - 1];

  int allocator::validate_linked_list(void * head) {
    if (head == NULL) return 0;

    if (PREV_PTR(head) != NULL) {
      printf("The block at location %p is the head of a linked list "
	     "but its previous pointer is not NULL.\n",
	     head);
      return -1;
    }
    
    void * prev = head;
    void * next = NEXT_PTR(head);
    while (next != NULL) {
      if (prev != PREV_PTR(next)) {
	printf("The block at location %p follows the block at location %p "
	       "in a linked list, but the previous pointer of %p is %p.\n",
	       next, prev, next, PREV_PTR(next));
	return -1;
      }
      
      prev = next;
      next = NEXT_PTR(next);
    }
    
    return 0;
  }

  int allocator::validate_free_list(int index) {
    void * head = freeLists[index];
    freeListCounter[index] = 0;

    if (head == NULL) return 0;
    
    int check_head = validate_free_block(head, index);
    if (check_head != 0) return check_head;
    
    // head is a block in this list.
    freeListCounter[index] = 1;
    if (PREV_PTR(head) != NULL) {
      printf("The block at location %p is the head of freeLists[%d]"
	     "but its previous pointer (%p) is not NULL.\n",
	     head, index, PREV_PTR(head));
      return -1;
    }
    
    void * prev = head;
    void * next = NEXT_PTR(head);
    while (next != NULL) {
      if (prev != PREV_PTR(next)) {
	printf("The block at location %p follows the block at location %p "
	       "in freeLists[%d], but the previous pointer of %p is %p.\n",
	       next, prev, index, next, PREV_PTR(next));
	return -1;
      }

      int check_next = validate_free_block(next, index);
      if (check_next != 0) return check_next;

      ++freeListCounter[index]; // found another block in list
      prev = next;
      next = NEXT_PTR(next);
    }
    
    return 0;
  }

  int allocator::validate_thread_free_list(int index) {
    void * head = threadFreeLists[index];
    threadFreeListCounter[index] = 0;

    if (head == NULL) return 0;
    
    int check_head = validate_thread_free_block(head, index);
    if (check_head != 0) return check_head;
    
    // head is a block in this list.
    threadFreeListCounter[index] = 1;
    if (PREV_PTR(head) != NULL) {
      printf("The block at location %p is the head of threadFreeLists[%d]"
	     "but its previous pointer (%p) is not NULL.\n",
	     head, index, PREV_PTR(head));
      return -1;
    }
    
    void * prev = head;
    void * next = NEXT_PTR(head);
    while (next != NULL) {
      if (prev != PREV_PTR(next)) {
	printf("The block at location %p follows the block at location %p "
	       "in threadFreeLists[%d], but the previous pointer of %p is %p.\n",
	       next, prev, index, next, PREV_PTR(next));
	return -1;
      }

      int check_next = validate_thread_free_block(next, index);
      if (check_next != 0) return check_next;

      ++threadFreeListCounter[index]; // found another block in list
      prev = next;
      next = NEXT_PTR(next);
    }
    
    return 0;
  }

  int allocator::validate_free_block(void * blockptr, int index) {
    size_t start_size_header = *(size_t *)blockptr;
    if (start_size_header & 1 != 1) {
      printf("The block at location %p in freeLists[%d] does not have the LSB "
	     "of the start size header (%zx) set to 1.\n",
	     blockptr, index, start_size_header);
      return -1;
    }
    
    size_t block_size = start_size_header & ~1;
    
    size_t end_size_header = *(size_t *)((uint8_t *)blockptr + 
					 block_size - sizeof(size_t));
    
    if (start_size_header != end_size_header) {
      printf("The block at location %p in freeLists[%d] does not have its starting "
	     "and ending size headers equal (%zx, %zx respectively).\n",
	     blockptr, index, start_size_header, end_size_header);
      return -1;
    }
    
    // check if this block's size is appropriate for this free list
    if (block_size >> LOG_MIN_SIZE + index != 1) {
      printf("The block at location %p in freeLists[%d] has size %zu, which does "
	     "not fall in the appropriate range for this free list "
	     "(%zu < size < %zu).\n",
	     blockptr, index, block_size, (size_t) 1 << LOG_MIN_SIZE + index,
	     (size_t) 1 << LOG_MIN_SIZE + index + 1);
      return -1;
    }

    return 0;
  }  

  int allocator::validate_thread_free_block(void * blockptr, int index) {
    size_t start_size_header = *(size_t *)blockptr;
    if (start_size_header & 1 != 1) {
      printf("The block at location %p in threadFreeLists[%d] does not have the LSB "
	     "of the start size header (%zx) set to 1.\n",
	     blockptr, index, start_size_header);
      return -1;
    }
    
    size_t block_size = start_size_header & ~1;
    
    size_t end_size_header = *(size_t *)((uint8_t *)blockptr + 
					 block_size - sizeof(size_t));
    
    if (start_size_header != end_size_header) {
      printf("The block at location %p in threadFreeLists[%d] does not have its starting "
	     "and ending size headers equal (%zx, %zx respectively).\n",
	     blockptr, index, start_size_header, end_size_header);
      return -1;
    }
    
    // check if this block's size is appropriate for this free list
    if (block_size >> LOG_MIN_SIZE + index != 1) {
      printf("The block at location %p in threadFreeLists[%d] has size %zu, which does "
	     "not fall in the appropriate range for this free list "
	     "(%zu < size < %zu).\n",
	     blockptr, index, block_size, (size_t) 1 << LOG_MIN_SIZE + index,
	     (size_t) 1 << LOG_MIN_SIZE + index + 1);
      return -1;
    }

    return 0;
  }  

  /*
   * check - This checks our invariant that the size_t header before every
   * block points to either the beginning of the next block, or the end of the
   * heap.
   *
   * Relies on the true assumption that we wrote perfect code to execute a perfect malloc.
   */
  int allocator::check()
  {
    for (int i = 0; i < NUM_FREE_LISTS - 1; ++i) {
      /*
       * Check all free lists to see that their internal structure is correct, and 
       * the elements in the lists are free, i.e. the last bit of the header and
       * footer size are 1.
       */
      int check_free_list_i = validate_free_list(i);
      if (check_free_list_i != 0) return check_free_list_i;
    }

    // do the same for threadFreeLists
    for (int i = 0; i < NUM_THREAD_FREE_LISTS - 1; ++i) {
      /*
       * Check all free lists to see that their internal structure is correct, and 
       * the elements in the lists are free, i.e. the last bit of the header and
       * footer size are 1.
       */
      int check_free_list_i = validate_thread_free_list(i);
      if (check_free_list_i != 0) return check_free_list_i;
    }

    // the last free list should always be (void *)-1 (sentinel indicating
    // wilderness case - heap must be expanded)
    if (freeLists[NUM_FREE_LISTS - 1] != (void *)-1) {
      printf("The last free list does not contain (void *)-1 (sentinel "
	     "indicating that the heap should be expanded)\n");
      return -1;
    }

    // same check for threadFreeLists
    if (threadFreeLists[NUM_THREAD_FREE_LISTS - 1] != (void *)-1) {
      printf("The last thread free list does not contain (void *)-1 (sentinel "
	     "indicating that the heap should be expanded)\n");
      return -1;
    }
    
    // validate memory blocks
    char *lo = (char *) mem_heap_lo();
    char *hi = (char*)mem_heap_hi() + 1;
    size_t size = 0;

    char* p = lo;
    while (lo <= p && p < hi) {
      /* 
       * Check the block beginning at p.
       * For all blocks:
       * - Check that the header size field matches the footer size field.
       *
       * If block is free:
       * - check that it is in the appropriate free list. If it is, then 
       *   increment the number of elements that belong in that free list
       *   found in memory
       *
       * If block is not free:
       * - check that the data is allocated to 8 bytes.
       *
       * Then, proceed to the next block based on size.
       */
      size = START_SIZE(p);

      // check header size field matches footer size field
      // this has already been done for free blocks but not for used blocks
      size_t start_size_header = *(size_t *)p;
      size_t end_size_header = *(size_t *)((uint8_t *)p + size - sizeof(size_t));
     
      if (start_size_header != end_size_header) {
	printf("The block at location %p does not have its starting "
	       "and ending size headers equal (%zx, %zx respectively).\n",
	       p, start_size_header, end_size_header);
	return -1;
      }

      // check if block is free
      if (IS_FREE(p)) {
	int index = FREE_LIST_INDEX(size);

	int check_in_free_list = is_in_free_list(p, index);
	//if (check_in_free_list != 0) return check_in_free_list;
	
	if (check_in_free_list == 0) --freeListCounter[index];
	else {
	  check_in_free_list = is_in_thread_free_list(p, index);
	  if (check_in_free_list != 0) return check_in_free_list;
	  else --threadFreeListCounter[index];
	}
      } else {
	// if the data is aligned then so is the pointer itself
	if (!IS_ALIGNED(p)) {
	  printf("The used block at location %p is not aligned to blocks of 8 bytes.\n",
		 p);
	}
      }

      // move to next block in memory
      p += size;
    }

    if (p != hi) {
      printf("Bad headers did not end at heap_hi!\n");
      printf("heap_lo: %p, heap_hi: %p, size: %lu, p: %p\n", lo, hi, size, p);
      return -1;
    } 

    /* 
     * Check if the number of free blocks found in memory match the number of
     * blocks in each free list.
     */
    for (int i = 0; i < NUM_FREE_LISTS - 1; ++i) {
      if (freeListCounter[i] != 0) {
	printf("Not all free blocks in freeLists[%d] were found in memory.\n",
	       i);
	return -1;
      }
    }

    // do the same check for threadFreeLists
    for (int i = 0; i < NUM_THREAD_FREE_LISTS - 1; ++i) {
      if (threadFreeListCounter[i] != 0) {
	printf("Not all free blocks in threadFreeLists[%d] were found in memory.\n",
	       i);
	return -1;
      }
    }
    return 0;
  }

  int allocator::is_in_free_list(void * blockptr, int index){
    void * next = freeLists[index];
    while (next != NULL) {
      if (blockptr == next) return 0;
      
      next = NEXT_PTR(next);
    }
    
    // don't print this - block may be in threadFreeLists
    /*
    printf("Block at location %p with size %zu was not found in freeLists[%d].\n",
	   blockptr, START_SIZE(blockptr), index);
    */
    return -1;
  }


  int allocator::is_in_thread_free_list(void * blockptr, int index){
    void * next = threadFreeLists[index];
    while (next != NULL) {
      if (blockptr == next) return 0;
      
      next = NEXT_PTR(next);
    }
    
    printf("Block at location %p with size %zu was not found in freeLists[%d] or "
	   "threadFreeLists[%d].\n",
	   blockptr, START_SIZE(blockptr), index, index);
    return -1;
  }
}
